package com.zklh.leetcode.tree.middle;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * @author ：tong nan
 * @date ：Created in 2021/4/25 17:43
 * @description ：构建最大二叉树
 * @modifiedBy ：
 */
public class MaximumBinaryTreeByArrayConstructor {



    public TreeNode construct(int[] arr) {

        return construct(arr, 0, arr.length-1);
    }


    // 先序遍历构建
    public TreeNode construct(int[] arr, int left ,int right) {
        if (left > right) {
            return null;
        }
        int maxIndex = left;
        int maxNumber = arr[left];

        for (int i = left+1; i < right+1; i++) {
            if (arr[i] > maxNumber) {
                maxIndex = i;
                maxNumber = arr[i];
            }
        }
        TreeNode nowNode = new TreeNode(maxNumber);
        nowNode.left = construct(arr,left, maxIndex-1);
        nowNode.right = construct(arr, maxIndex+1, right);
        return nowNode;
    }

    public static void main(String[] args) {
        int[] arr = {3,2,1,6,0,5};
        MaximumBinaryTreeByArrayConstructor maximumBinaryTreeByArrayConstructor = new MaximumBinaryTreeByArrayConstructor();
        TreeNode root = maximumBinaryTreeByArrayConstructor.construct(arr);

    }
}
